#include <iostream>
#include <map>
#include <stdint.h>
#include <cmath>
#include "hash.h"

using namespace std;

void printAvgAndStdDev(const map<hash_t, int>& hashes) {
	double sum = 0;
	double sum2 = 0;
	double hsum = 0;
	double hsum2 = 0;

	for (map<hash_t, int>::const_iterator i = hashes.begin(); i != hashes.end(); ++i) {
		sum += i->second;
		sum2 += i->second * (double) i->second;
		hsum += i->second * (double) i->first;
		hsum2 += i->second * (double) i->first * i->first;
	}

	double avg = sum / hashes.size();
	double stddev = sqrt(sum2 / hashes.size() - avg * avg);
	double havg = hsum / sum;
	double hstddev = sqrt(hsum2 / sum - havg * havg);
	cout << "filled " << sum << " in " << hashes.size() << " (uniform avg: " << (sum / hashes.size()) << ") avg: " << avg << " stddev: " << stddev << " havg: " << havg << " hstddev: " << hstddev << "\n";
}

int main() {
	const hash_t N = 1 << 20;
	int x = 0;

	map<hash_t, int> hashes;
	hash_t h = 0;
	uint64_t i = 0;

	while (x != -1) {
		h = hash<int32_t>(x, hash<int32_t>(x + 1, 0));
		++hashes[h % N];

		if (++i % 100000 == 10000)
			printAvgAndStdDev(hashes);

		++x;
	}

	cout << "FINISHED!\n";
	printAvgAndStdDev(hashes);

	return 0;
}
